package com.dyz.leetcode._05_sort;

import java.util.ArrayList;

public class _57_insert {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int i = 0;
        ArrayList<int[]> res = new ArrayList();
        //1. 将区间结束小于新区间开始的区间放入到结果集
        while(i<intervals.length && intervals[i][1]<newInterval[0]){
            res.add(intervals[i]);
            i++;
        }
        // 2. 将区间开始小于等于新区间结束的区间和新区间合并
        while(i<intervals.length && intervals[i][0]<=newInterval[1]){
            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
            i++;
        }
        // 3. 将合并后的区间加入道结果集
        res.add(newInterval);
        // 4. 将剩余的区间放入到结果集
        while(i<intervals.length){
            res.add(intervals[i]);
            i++;
        }
        return res.toArray(new int[res.size()][]);
    }
}
